perm filename EULER.5[0,BGB] blob
sn#076501 filedate 1974-02-14 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00004 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 SUMMARY OF POLYHEDRON PRIMITIVES.
C00005 00003 PRIMITIVES ON POLYHEDRA.
C00009 00004 Euler Primitives.
C00013 ENDMK
C⊗;
SUMMARY OF POLYHEDRON PRIMITIVES.
A. EULER PRIMITIVES.
1. BNEW ← MKBFV; make a body, face & vertex.
2. KLBFEV(Q); kill a body & all its pieces.
3. VNEW ← MKEV(F,V); make edge & vertex.
4. ENEW ← MKFE(V1,F,V2); make face & edge.
5. VNEW ← ESPLIT(E); split an edge.
6. F ← KLFE(ENEW); kill face & edge leaving a face.
7. E ← KLEV(VNEW); kill edge & vertex leaving an edge.
8. V ← KLVE(ENEW); kill vertex & edge leaving a vertex.
9. B ← GLUE(F1,F2); glue two faces together.
* 10. BNEW ← UNGLUE(E); unglue along a seam containing E.
B. SOLID PRIMITIVES.
1. VPEAK ← PYRAMID(F); form a pyramid on a face.
2. F ← PRISM(F); form a rectangular prism.
3. F ← CWPRISMOID(F) form a clockwise prismoid.
4. F ← CCWPRISMOID(F); form a counter clockwise prismoid.
5. ROTCOM(F); complete a solid of rotation.
6. FVDUAL(B); form face vertex dual of a body.
7. BNEW ← MKCOPY(B); make a copy of a body.
8. EVERT(B); turn a body surface inside out.
9. B1 ← BUN(B1,B2); form union of body interiors.
10. B1 ← BIN(B1,B2); form intersection of body interiors.
C. GEOMETRIC PRIMITIVES.
1. TRANSLATE(Q,R);
2. ROTATE(Q,R);
3. DILATE(Q,R);
4. REFLECT(Q,R);
D. IMAGE PRIMITIVES.
1. PROJECTOR(CAMERA,WORLD);
2. ELIST←CLIPER(WINDOW,WORLD);
3. OCCULT(WORLD);
* 4. SHADOW(SUN,WORLD);
* 5. TV ← MKVID(WINDOW,WORLD);
* 6. B2D ← MKB2D(WINDOW,WORLD);
* 7. B2D ← CAREYE(TV);
* under construction, Oct 1972.
PRIMITIVES ON POLYHEDRA.
In this section a number of primitives for doing things to
polyhedra are explained. Although these primitives are currently
implemented using the winged edge data structure, they do not require
a particular polyhedron representation. Indeed, many of these
primitives were originally implemented in a LEAP polyhedron
representation very similar to that of Falk, Feldman and Paul
[reference 5]. Thus, the primitives of this section are on a level
logically independent from the operations of the previous section.
Another aspect of these primitives is that they can be used
as the basis of a "graphics language" or more accurately as a package
of subroutines for geometric modeling. In this vein, the primitives
are currently collected as a package called GEOMES for Geometric
Modeling Embedded in SAIL; and as GEOMEL, Geometric Modeling Embedded
in LISP. A third language, called GEOMED, arises out of the command
language of a geometric model editor based on the primitives.
The primitives are shown in four groups in the summary. The
first group, the Euler Primitives, were inspired by Coxeter's proof
of Euler's formula, section 10.3 of [reference 2]. Although the proof
only required three primitives, additional ones of the same ilk were
developed for convenience. The second group is composed of some
polyhedron primitives that were coded using the Euler primitives. The
third group is for primitives that move bodies, faces, edges and
vertices; or compute geometric values such as length and volume. This
group is underdeveloped for two reasons: one, because I have done
these computations ad hoc to date; and two, because they imply the
subject of animation which is large and difficult and not of central
importance to vision. With the exception of the camera, my worlds are
nearly (but not absolutely) static. A less impoverished geometric
group will be presented in the future. The final group, has three
well developed primitives for making 2D images; and several
primitives that when finished will realize part of the vision system
that I am trying to build.
Euler Primitives.
As mention above, the Euler primitives are based on the Euler
Equation F-E+V = 2*B-2*H; where F, E, V, B and H stand for the number
of faces, edges, vertices, bodies and handles that exist. The term
"handle" comes from topology, and is the number of well formed holes
in a surface; a sphere has no handles, a torus has one handle, and an
IBM flowcharting template has 26 handles. The Euler equation
restricts the possible topologies of FEV graphs that can be
polyhedra; although such Eulerian polyhedra do not necessarily
correspond to what we normally call a solid classical polyhedron.
Strict adherence to constructing a polyhedron that satisfies Euler
equation F-E+V = 2*B - 2*H would require only four primitives:
+F -E +V = 2*B - 2*H
1. Make Body, Face and Vertex +1....+1....+1......
2. Make Edge and Vertex. ...-1 +1............
3. Make Face and Edge. +1 -1...............
4. Glue two faces of one body. -2 +N -N..........+1
4.' Glue two faces of two bodies. -2 +N -N....-1......
However, the four corresponding destructive primitives are also
possible and desirable:
+F -E +V = 2*B - 2*H
1. Kill Body, Face and Vertex -1....-1....-1......
2. Kill Edge and Vertex. ...+1 -1............
3. Kill Face and Edge. -1 +1...............
4. Unglue along a seam. +2 -N +N..........-1
4.' Unglue along a seam. -2 +N -N....+1......
And finally the operation of splitting an edge at a midpoint into two
edges became so important in forming T-joints during hidden line
elimination that the ESPLIT primitive was introduced in place of the
equivalent KLFE, MKEV, MKFE sequence.
In using the Euler primitives, some non-classical polyhedra
are tolerated as transitional states of the construction; these
transitional states are called:
Seminal Polyhedron.
Wire Polyhedron.
Lamina Polyhedron.
Shell Polyhedron.
Face with Wire Spurs on its perimeter.
A seminal polyhedron is like a point; a wire polyhedron is linear
with two ends like a single piece of wire; lamina and shell polyhedra
are surfaces, and the picturesque phrase about spurs is a restriction
on how faces are dissected into more faces. These terms will be
explained in more detail when they are needed.